Nested stack automaton
In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an indexed language.[2]
See also
References
- ^ Aho, Alfred (1969). "Nested stack automata". Journal of the ACM 16 (3): 383–406. doi:10.1145/321526.321529. ISSN 0004-5411. http://portal.acm.org/ft_gateway.cfm?id=321529&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=21501966&CFTOKEN=95121590.
- ^ Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
|
|
|
|
|
|
|
Type-0
|
|
|
—
|
|
|
Type-1
|
|
|
—
|
|
|
—
|
|
|
—
|
|
|
Type-2
|
|
|
—
|
|
|
—
|
|
|
Type-3
|
|
|
—
|
|
|
|
|
|
|
|
|
(no common name)
|
|
|
|
|
|
|
|
|
Linear context-free rewriting systems etc.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
—
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nested stack
|
|
|
Thread automata
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Each category of languages is a proper subset of the category directly above it. - Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.
|
|